package com.yww.algorithm.recursion;

import com.yww.datastructure.line.Linear;
import com.yww.datastructure.line.linkedlist.CircularLinkedList;
import com.yww.datastructure.line.linkedlist.DoubleLinkedList;
import com.yww.datastructure.line.linkedlist.SingleLinkedListSentinel;

/**
 * @author yww
 * @description 汉诺塔 递归求解
 * @since 2024/1/31 16:47
 */
public class HanoiTower {
    // 三根柱子 a b c
    Linear<Integer> a = new CircularLinkedList<>();
    Linear<Integer> b = new SingleLinkedListSentinel<>();
    Linear<Integer> c = new DoubleLinkedList<>();

    // 初始方法，先将所有盘放置a
    public void init(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    /**
     * 汉诺塔移盘
     *
     * @param n 移动第几个盘
     * @param a 源
     * @param b 借
     * @param c 目
     **/
    public void move(int n, Linear<Integer> a, Linear<Integer> b, Linear<Integer> c) {
        if (n == 0) {
            return;
        }
        // 先将 a 上面的n-1个盘，从 a 借助于 c 移动到 b
        move(n - 1, a, c, b);
        // 将最后一个盘，从 a 移动到 c
        c.addLast(a.removeLast());
        print();
        // 再将 b 上的n-1个盘，借助于 a 移动到 c
        move(n - 1, b, a, c);

    }

    public void print() {
        System.out.println("--------------------移动结果--------------------");
        System.out.println("a柱：" + a.asString());
        System.out.println("b柱：" + b.asString());
        System.out.println("c柱：" + c.asString());
    }

    public static void main(String[] args) {
        HanoiTower hanoiTower = new HanoiTower();
        hanoiTower.init(4);
        hanoiTower.move(4, hanoiTower.a, hanoiTower.b, hanoiTower.c);
    }

}
